const double eps = 1e-12;
struct Point {
	Point() {}
	Point(int x_, int y_) : x(x_), y(y_) {}
	Point(double x_, double y_) : x(x_), y(y_) {}

	friend Point operator+(Point a, Point b) {
		return Point(a.x + b.x, a.y + b.y);
	}
	friend Point operator-(Point a, Point b) {
		return Point(a.x - b.x, a.y - b.y);
	}
	friend Point operator*(Point a, double t) {
		return Point(a.x * t, a.y * t);
	}
	friend double dis(Point a, Point b) {
		return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	}
	double x, y;
};
struct Vector {
	Vector() {}
	Vector(Point p_) : p(p_) {}

	Vector operator*(double t) {
		return Vector(p * t);
	}
	
	friend double operator*(Vector a, Vector b) {
		return a.p.x * b.p.x + a.p.y * b.p.y;
	}
	friend double dot(Vector a, Vector b) {
		return a * b;
	}
	friend double len(Vector a) {
		return sqrt(a * a);
	}
	friend double angle(Vector a, Vector b) {
		return acos(dot(a, b) / len(a) / len(b));
	}
	friend double cross(Vector a, Vector b) {
		return a.p.x * b.p.y - a.p.y * b.p.x;
	}
	Point p;
};
struct Line {
	Line() {}
	Line(Point a_, Point b_) : pa(a_), pb(b_) {}

	friend bool line_intersection_seg(Line a, Line b) { 
		double d1 = cross(Vector(a.pb - a.pa), Vector(b.pa - a.pa));
		if (fabs(d1) < eps) {
			return true;
		}
		double d2 = cross(Vector(a.pb - a.pa), Vector(b.pb - a.pa));
		if (fabs(d2) < eps) {
			return true;
		}
		return (d1 > 0 ? 1 : 0) ^ (d2 > 0 ? 1 : 0);
	}
	friend bool seg_intersection_seg(Line a, Line b) {
		return line_intersection_seg(a, b) && line_intersection_seg(b, a);
	}
	friend Point line_intersection_line(Line &a, Line &b) {
		Vector u(a.pb - a.pa), v(b.pb - b.pa);
		double t = Vector(a.pa - b.pa) * v / (u * v);
		return a.pa + (u * t).p;
	}
	Point pa, pb;
};